package com.dsz.day5.dfs_bfs;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
//处理这个问题的的基础知识：邻接表
public class Solution {
    private HashMap<String,EdgeNode> nodeMap=new HashMap();

    //创建邻接表
    public void insertNode(String n1,String n2){
        EdgeNode edgeNode1 = nodeMap.get(n1);
        EdgeNode edgeNode2 = nodeMap.get(n2);
        if (edgeNode1==null) {
            edgeNode1 = new EdgeNode(n1);
            nodeMap.put(n1,edgeNode1);
        }
        if (edgeNode2==null){
            edgeNode2 = new EdgeNode(n2);
            nodeMap.put(n2,edgeNode2);
        }
        LinkedList linkedList1=edgeNode1.getEdgeNodeList();
        LinkedList linkedList2=edgeNode2.getEdgeNodeList();
        if(linkedList1==null) {
            linkedList1 = new LinkedList();
        }
        if (linkedList2==null){
            linkedList2=new LinkedList();
        }
        linkedList1.addLast(edgeNode2);
        linkedList2.addLast(edgeNode1);
        edgeNode1.setEdgeNodeList(linkedList1);
        edgeNode2.setEdgeNodeList(linkedList2);
    }
    //获取邻接表并打印
    public void getNodeMap(){
        for (Map.Entry<String,EdgeNode> entry:nodeMap.entrySet()){
            System.out.print(entry.getKey());
            Iterator<EdgeNode> iterator=entry.getValue().getEdgeNodeList().iterator();
            while (iterator.hasNext()){

                System.out.print("->"+iterator.next().getName());
            }
            System.out.println();
        }

    }

    //深度遍历图
    public void dfs(String firstEdgeNodeName){
        EdgeNode currentNode = nodeMap.get(firstEdgeNodeName);
        if (!currentNode.isVisited()) {
            //对结点进行相关操作
            System.out.print(currentNode.getName()+"->");
            //设置结点为已访问
            currentNode.setVisited(true);
            Iterator<EdgeNode> iterator = currentNode.getEdgeNodeList().iterator();
            while (iterator.hasNext()) {
                dfs(iterator.next().getName());
            }
        }
        else {
            return;
        }
    }

    //广度遍历图
    public void bfs(String firstEdgeNodeName){
        LinkedList<EdgeNode> queue=new LinkedList<>();
        queue.add(nodeMap.get(firstEdgeNodeName));
        while (!queue.isEmpty()){
            EdgeNode currentNode=queue.removeFirst();
            if (currentNode.isVisited()){
                continue;
            }
            System.out.print(currentNode.getName()+"->");
            currentNode.setVisited(true);
            for (EdgeNode sonNode: currentNode.getEdgeNodeList()){
                if (!sonNode.isVisited()){
                    queue.add(sonNode);
                }
            }
        }
    }
    //初始化访问结点，即设置所以结点都为未访问
    public void setVisit(){
        //用于遍历nodeMap.entrySet()集合，每次迭代时，entry变量会被赋值为集合中的一个条目
        //这样可以在循环体中，通过entry访问每个键值对的键和值
        for (Map.Entry<String,EdgeNode> entry:nodeMap.entrySet()){

            //获取每个条目的值即EdgeNode对象，并调用setVisited方法，将访问状态设置false
            //表示该节点未被访问
            entry.getValue().setVisited(false);
        }
    }
}
